package 极客算法训练营.chapter09;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
 * <p>
 * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 * <p>
 * 此外，你可以假设该网格的四条边均被水包围
 */
public class 岛屿数量 {

    class Solution1 {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            int row = grid.length;
            int col = grid[0].length;
            int island = 0;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == '1') {
                        island++;
                        dfs(grid, i, j);
                    }
                }
            }
            return island;
        }

        private void dfs(char[][] grid, int row, int col) {
            if (row < 0 || col < 0 || row >= grid.length || col >= grid[0].length || grid[row][col] == '0') {
                return;
            }
            grid[row][col] = '0';
            dfs(grid, row - 1, col);
            dfs(grid, row + 1, col);
            dfs(grid, row, col - 1);
            dfs(grid, row, col + 1);
        }
    }

    static class Solution {
        public int numIslands(char[][] grid) {
            if (grid == null || grid.length == 0) {
                return 0;
            }
            int row = grid.length;
            int col = grid[0].length;
            int island = 0;
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == '1') {
                        island++;
                        grid[i][j] = '0';//找到就应该第一时间标记
                        Deque<Integer> queue = new ArrayDeque<>();
                        queue.addLast(i * col + j);
                        while (!queue.isEmpty()) {
                            int size = queue.size();
                            for (int k = 0; k < size; k++) {
                                Integer pop = queue.pollFirst();
                                int _row = pop / col;
                                int _col = pop % col;
//                                grid[_row][_col] = '0';//找到就应该第一时间标记，对于相邻元素，就会进行重复性添加
                                //上
                                if (_row - 1 >= 0 && grid[_row - 1][_col] == '1') {
                                    queue.addLast((_row- 1) * col + _col);
                                    grid[_row - 1][_col] = '0';
                                }
                                //下
                                if (_row + 1 < row && grid[_row + 1][_col] == '1') {
                                    queue.addLast((_row + 1) * col + _col);
                                    grid[_row + 1][_col] = '0';
                                }
                                //左
                                if (_col - 1 >= 0 && grid[_row][_col - 1] == '1') {
                                    queue.addLast(_row * col + _col - 1);
                                    grid[_row][_col - 1] = '0';
                                }
                                //右
                                if (_col + 1 < col && grid[_row][_col + 1] == '1') {
                                    queue.addLast(_row * col + _col + 1);
                                    grid[_row][_col + 1] = '0';
                                }
                            }
                        }
                    }
                }
            }
            return island;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] grid = new char[][]{{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}};
        int count = solution.numIslands(grid);
        System.out.println(count);
    }
}
